package org.example.Greedy_Algorithm;

import java.util.ArrayList;

public class Monotonically_increasing_numbers {
    public static void main(String[] args) {
        //单调递增的数字

        //当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
        //给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
        int n = 10;
        int i = monotoneIncreasingDigits(n);
        System.out.println(i);
    }
    //1ms,不愧是国服
    public static int monotoneIncreasingDigits(int n) {
        ArrayList<Integer> list = new ArrayList<>();
        while(n/10>=1){
            int num = n % 10;
            list.add(num);
            n = n/10;
        }
        list.add(n);
        StringBuilder sb = new StringBuilder();
        while(true){
            boolean flag = true;
            int j;
            for (j = list.size()-1; j >= 0; j--) {
                if (j!=0 && list.get(j)>list.get(j-1)){
                    flag = false;
                    break;
                }
            }
            if (!flag){
                for (int i = 0; i < list.size(); i++) {
                    if (i==j){
                        Integer num = list.get(j);
                        num = num - 1;
                        list.set(j,num);
                        break;
                    }
                    list.set(i,9);
                }
            }
            if (flag) break;
        }
        for (int i = list.size()-1; i >=0 ; i--) {
            sb.append(list.get(i));
        }
        return Integer.parseInt(sb.toString());
    }
    //超出时间限制
    public static int monotoneIncreasingDigits2(int n) {
        for (int i = n; i >= 0; i--) {
            if (getNumber2(i)){
                return i;
            }
        }
        return 0;
    }

    public static boolean getNumber2(int i){
        ArrayList<Integer> list = new ArrayList<>();
        while(i/10>=1){
            int num = i % 10;
            list.add(num);
            i = i/10;
        }
        list.add(i);
        for (int j = 0; j < list.size(); j++) {
            if (j!=list.size()-1 && list.get(j)< list.get(j+1)){
                return false;
            }
        }
        return true;
    }
}
